package com.leetcode.leetcode1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *   电话号码的字母组合
 * @author: luhd
 * @create: 2021-08-27
 */
public class Practice17 {
    public static void main(String[] args) {
        String digits = "23";
        List<String> strings = letterCombinations(digits);
        System.out.println(strings);
    }
    public static List<String> letterCombinations(String digits) {
        //char[] key = {2,3,4,5,6,7,8,9};
        //String[] value = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        List<String> combinations= new ArrayList<>();
        if(digits.length()==0) return combinations;
        HashMap<Character, String> hm = new HashMap<>();
        hm.put('2',"abc");
        hm.put('3',"def");
        hm.put('4',"ghi");
        hm.put('5',"jkl");
        hm.put('6',"mno");
        hm.put('7',"pqrs");
        hm.put('8',"tuv");
        hm.put('9',"wxyz");
        int len = digits.length();
        backtrack(combinations,hm,digits,0,new StringBuffer());
        return combinations;
    }
    // 找出所有组合，想到需要用到回溯算法
    public static void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if(index==digits.length()){
            combinations.add(combination.toString());
        }else{
            // 拿到数字
            char digit = digits.charAt(index);
            // 拿到数字对应的字符串
            String letters = phoneMap.get(digit);
            // 字符串的长度
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                // StringBuffer 里添加字符串的一位
                combination.append(letters.charAt(i));
                // 递归，上一条语句 会和 递归里的上一条  拼接起来   形成最终的结果
                backtrack(combinations,phoneMap,digits,index+1,combination);    //  [ad, ade, adef, adefbd, adefbde, adefbdef, adefbdefcd, adefbdefcde, adefbdefcdef]
                // a 和 def配  ad-->index=2 所以ad放入结果集  下一行代码就是删除d 即 a和e拼接ae 放入结果集  再删除e  再拼接f 再删除f 再跳出循环 再删除a
                combination.deleteCharAt(index);
            }
        }
    }
}
